{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Лекция 6. Контейнеры и итераторы"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://en.cppreference.com/w/cpp/container"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://apprize.info/c/optimized/10.html"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Что такое контейнер и что такое итератор общими словами:\n",
    "* контейнер - хранилище объектов одного типа\n",
    "* итератор - \"ключик\" к конкретному объекту в контейнере, возможно, позволяющий \"обходить\" контейнер - перечислять объекты в нём"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "// контейнер целых чисел\n",
    "std::vector<int> v = {1, 2, 3, 4, 5};\n",
    "\n",
    "// итератор, указывающий на нулевой элемент в контейнере:\n",
    "std::vector<int>::iterator it = v.begin();\n",
    "// auto it = v.begin();  // или так, компилятор сам выведет тип\n",
    "\n",
    "++it;  // теперь it указывает на первый элемент в контейнере\n",
    "\n",
    "*it = 42;\n",
    "\n",
    "std::cout << v[1]; // # 42\n",
    "v[1] = 55;\n",
    "std::cout << *it; // # 55\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Вопросы__:\n",
    "* с какими контейнерами мы уже имели дело в курсе?\n",
    "\n",
    "<details>\n",
    "<summary>Подсказка</summary>\n",
    "<p>\n",
    "\n",
    "`std::string`\n",
    "\n",
    "</p>\n",
    "</details>\n",
    "\n",
    "* какие ещё контейнеры вы знаете?\n",
    "* владеет ли контейнер объектами в нём? (про что этот вопрос?)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Стандартные контейнеры: последовательности"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Памятка: обратить _особое_ внимание на внутреннюю организацию, `sizeof`, детали реализации, стоимость операций."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://en.cppreference.com/w/cpp/container/array\n",
    "\n",
    "Массив:\n",
    "* compile-time размер\n",
    "* объекты размещены непосредственно в `std::array`\n",
    "* объекты размещены последовательно"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "// example\n",
    "template<typename T, size_t N>\n",
    "class array\n",
    "{\n",
    "private:\n",
    "    T data_[N];\n",
    "\n",
    "    ...;    \n",
    "};\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Важнейшее свойство `std::array`, которое выделяет его на фоне всех других контейнеров - отсутствие аллокаций внутри контейнера:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "void func()\n",
    "{\n",
    "    // 5 целых чисел будут отмотаны НА СТЕКЕ, никаких вызовов malloc\n",
    "    std::array<int, 5> arr;\n",
    "    arr[2] = 0;\n",
    "    arr[3] = 0;\n",
    "    \n",
    "    // добро пожаловать в динамическую память, malloc-free\n",
    "    // и прочие радости медленного кода \n",
    "    std::vector<int> v = {1, 2, 3, 4, 5};\n",
    "    \n",
    "    // ну оооооооок, в динамической памяти\n",
    "    auto* p = new std::array<int, 5>();\n",
    "    ...\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Стоимость:\n",
    "* расходы памяти на i-ый элемент - ???\n",
    "* доступ до i-го элемента - ???\n",
    "* поиск по значению - ???\n",
    "* вставка - ???\n",
    "* удаление - ???\n",
    "* сортировка - ???\n",
    "* sizeof - ???"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://en.cppreference.com/w/cpp/numeric/valarray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* фиксированный размер в runtime (но можно менять через `resize`)\n",
    "* выделение памяти на куче\n",
    "* объекты размещены последовательно\n",
    "* оптимизирован под мат.операции (в плане интерфейса и реализации)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "float f(unsigned n)\n",
    "{\n",
    "    std::valarray<float> v1(1.f, n);\n",
    "    std::valarray<float> v2(2.f, n);\n",
    "    \n",
    "    // рассмотрим два примера использования,\n",
    "    // что в них происходит, какой из них быстрее?\n",
    "    \n",
    "    // ex.1\n",
    "    auto v3 = v1 * 2.f + v2;\n",
    "    \n",
    "    // ex.2\n",
    "    auto v4 = v1;\n",
    "    v4 *= 2.f;\n",
    "    v4 += v2;\n",
    "    \n",
    "    return v4.sum();\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Как организован внутри?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Стоимость:\n",
    "* расходы памяти на i-ый элемент - ???\n",
    "* доступ до i-го элемента - ???\n",
    "* поиск по значению - ???\n",
    "* вставка - ???\n",
    "* удаление - ???\n",
    "* сортировка - ???\n",
    "* sizeof - ???"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://en.cppreference.com/w/cpp/container/vector"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "http://www.cvl.isy.liu.se:82/education/graduate/opencv/pres.pdf"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* меняющийся размер\n",
    "* выделение памяти на куче\n",
    "* объекты размещены последовательно"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "int f()\n",
    "{\n",
    "    std::vector<int> v1 = {1, 2, 3, 4, 5};\n",
    "    v1.push_back(6);\n",
    "    v1.push_back(7);\n",
    "    v1.push_back(8);\n",
    "    \n",
    "    v1.clear();\n",
    "    v1.push_back(9);\n",
    "    v1.insert(v1.begin(), 1);\n",
    "    \n",
    "    return v1.back();\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "std::vector<int> v = {1, 2, 3};\n",
    "v.first(); // 1\n",
    "v.back(); // 3\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](vector_internals.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Эта история будет вечной..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "// ex 1\n",
    "std::vector<int> v1;\n",
    "for (int i = 0; i < N; ++i)\n",
    "    v1.push_back(i);\n",
    "// Вопрос: сложность алгоритма в кол-ве копирований\n",
    "// Вопрос: сложность алгоритма в кол-ве аллокаций\n",
    "    \n",
    "// ex 2\n",
    "std::vector<int> v2;\n",
    "v2.reserve(N);\n",
    "for (int i = 0; i < N; ++i)\n",
    "    v1.push_back(i);\n",
    "// Вопрос: сложность алгоритма в кол-ве копирований\n",
    "// Вопрос: сложность алгоритма в кол-ве аллокаций\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Стоимость:\n",
    "* расходы памяти на i-ый элемент - ???\n",
    "* доступ до i-го элемента - ???\n",
    "* поиск по значению - ???\n",
    "* вставка в начало - ???\n",
    "* вставка в середину - ???\n",
    "* вставка в конец - ???\n",
    "* удаление - ???\n",
    "* сортировка - ???\n",
    "* sizeof - ???"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Специальное исключение:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "std::vector<bool> bv;\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://en.cppreference.com/w/cpp/container/deque"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* меняющийся размер\n",
    "* выделение памяти на куче\n",
    "* объекты размещены последовательными блоками, а блоки раскиданы по памяти"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Нарисовать как хранится `deque`: блоки + переходы (bookkeeping)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](deque_internals.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Размер блока зависит от реализации: \n",
    "* times the object size on 64-bit libstdc++;\n",
    "* 16 times the object size or 4096 bytes, whichever is larger, on 64-bit libc++"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "std::deque<int> d = {1, 2, 3, 4 ,5};\n",
    "        \n",
    "d.push_back(6);\n",
    "d.push_front(0);\n",
    "\n",
    "d.pop_back();\n",
    "d.pop_front();\n",
    "\n",
    "d[2] = 3;\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Стоимость:\n",
    "* расходы памяти на i-ый элемент - ???\n",
    "* доступ до i-го элемента - ???\n",
    "* поиск по значению - ???\n",
    "* вставка в начало - ???\n",
    "* вставка в середину - ???\n",
    "* вставка в конец - ???\n",
    "* удаление - ???\n",
    "* сортировка - ???\n",
    "* sizeof - ???"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://en.cppreference.com/w/cpp/container/list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* меняющийся размер\n",
    "* выделение памяти на куче отдельно под каждый элемент\n",
    "* оптимизирован под вставку / удаление элементов в произвольном месте"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](list_internals.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "std::list<int> l = { 7, 5, 16, 8 };\n",
    "l.push_back(4);\n",
    "l.push_front(3);\n",
    "\n",
    "l.sort();\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Стоимость:\n",
    "\n",
    "* расходы памяти на i-ый элемент - ???\n",
    "* доступ до i-го элемента - ???\n",
    "* поиск по значению - ???\n",
    "* вставка в начало - ???\n",
    "* вставка в середину - ???\n",
    "* вставка в конец - ???\n",
    "* удаление - ???\n",
    "* сортировка - ???\n",
    "* sizeof - ???"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://en.cppreference.com/w/cpp/container/forward_list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Вариант `std::list` с урезанным функционалом, но более дешёвый по памяти."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](forwardlist_internals.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "std::forward_list<int> f = {1, 2, 3, 4, 5};\n",
    "f.push_front(0);\n",
    "f.insert_after(f.begin(), 1);\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Стоимость:\n",
    "\n",
    "* расходы памяти на i-ый элемент - ???\n",
    "* доступ до i-го элемента - ???\n",
    "* поиск по значению - ???\n",
    "* вставка в начало - ???\n",
    "* вставка в середину - ???\n",
    "* вставка в конец - ???\n",
    "* удаление - ???\n",
    "* сортировка - ???\n",
    "* sizeof - ???"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Стандартные контейнеры: ассоциативные"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://en.cppreference.com/w/cpp/container/map\n",
    "\n",
    "https://en.cppreference.com/w/cpp/container/set\n",
    "\n",
    "https://en.cppreference.com/w/cpp/container/multimap\n",
    "\n",
    "https://en.cppreference.com/w/cpp/container/multiset"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Отображения / множества, основанные на порядке элементов. Обычно реализуются в виде красно-чёрных деревьев по ключам."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Главное требование к ключам - они должны иметь порядок с требованиями Compare (strict weak ordering + equivalence https://en.cppreference.com/w/cpp/named_req/Compare):\n",
    "* либо определён `operator<` для ключей, удовлетворящий требованиям Compare\n",
    "* либо специфицирована пользовательская функция сравнения, удовлетворящия требованиям Compare\n",
    "\n",
    "Замечание: если сравнение не удовлетворяет требованиям Compare - UB"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Важное свойство: порядок обхода объектов - отсортированы по ключу."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "// создание отображения\n",
    "std::map<int, std::string> id_to_name = {\n",
    "    {73, \"Balin\"},\n",
    "    {42, \"Dwalin\"},\n",
    "    {55, \"Gloin\"}\n",
    "};\n",
    "\n",
    "// добавление элементов:\n",
    "id_to_name[53] = \"Gimli\";\n",
    "\n",
    "// изменение:\n",
    "id_to_name[53] = \"Torin\";\n",
    "\n",
    "// особенность map-подобных контейнеров: operator[] создаёт элемент, если его там нет\n",
    "const std::string name = id_to_name[54]; // # name == \"\", но в id_to_name теперь есть такой элемент: {54, \"\"}\n",
    "        \n",
    "// перебор элементов (порядок!!)\n",
    "{\n",
    "    // так код не пишите, это до С++11\n",
    "    for(std::map<int, std::string>::iterator it = id_and_name.begin(); it != id_and_name.end(); ++it)\n",
    "        std::cout << it->first << \" \" << it->second << std::endl;\n",
    "\n",
    "    // так код не пишите, только для иллюстрации\n",
    "    for (const std::pair<const int, std::string>& id_and_name : id_to_name)\n",
    "        std::cout << id_and_name.first << \" \" << id_and_name.second << std::endl;\n",
    "    \n",
    "    // если не разрешён С++17, то хотя бы так\n",
    "    for (const auto& id_and_name : id_to_name)\n",
    "        std::cout << id_and_name.first << \" \" << id_and_name.second << std::endl;\n",
    "    \n",
    "    // начиная с С++17:\n",
    "    for (const auto& [id, name] : id_to_name)\n",
    "        std::cout << id << \" \" << name << std::endl;\n",
    "}\n",
    "\n",
    "// поиск элемента в map\n",
    "{\n",
    "    // до С++11\n",
    "    std::map<int, std::string>::iterator it = id_to_name.find(42);\n",
    "    if (it != id_to_name.end())\n",
    "        std::cout << it->first;\n",
    "    \n",
    "    // после C++11\n",
    "    auto it = id_to_name.find(42);\n",
    "    if (it != id_to_name.end())\n",
    "        std::cout << it->second;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "std::set<std::string> animals = {\"cat\", \"dog\", \"dolphin\"};\n",
    "animals.insert(\"elephant\");\n",
    "animals.erase(\"dragon\");\n",
    "\n",
    "// !порядок\n",
    "for (const auto& animal : animals)\n",
    "    std::cout << animal << std::endl;\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](set_internals.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Задание оператора сравнения:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "// пользовательский тип\n",
    "struct Point\n",
    "{\n",
    "    float x, y;\n",
    "};\n",
    "\n",
    "// определяем понятие меньше через лексикографическое сравнение\n",
    "bool operator < (const Point& l, const Point& r) noexcept\n",
    "{\n",
    "    return std::tie(l.x, l.y) < std::tie(r.x, r.y);\n",
    "}\n",
    "\n",
    "// теперь можно делать set/map:\n",
    "std::set<Point> points;\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "// пользовательский тип\n",
    "struct Person\n",
    "{\n",
    "    std::string name;\n",
    "    int age;\n",
    "};\n",
    "\n",
    "// не хотим определять operator< или хотим отличную от него сортировку в set\n",
    "struct LessPersionByAge\n",
    "{\n",
    "    bool operator()(const Person& l, const Person& r) const noexcept\n",
    "    {\n",
    "        return std::tie(l.age, l.name) < std::tie(r.age, r.name);\n",
    "    }\n",
    "};\n",
    "\n",
    "// теперь можно:\n",
    "std::set<Person, LessPersionByAge> people;    \n",
    "\n",
    "// продвинутый вариант, почему он работает - рассмотрим, когда будем работать с лямбдами:\n",
    "auto less_persion_by_age = [](const Person& l, const Person& r) {\n",
    "    return std::tie(l.age, l.name) < std::tie(r.age, r.name);\n",
    "};\n",
    "set::set<Person, decltype(less_persion_by_age)> people;\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Стоимость:\n",
    "\n",
    "* расходы памяти на элемент - ???\n",
    "* поиск по значению - ???\n",
    "* вставка - ???\n",
    "* удаление - ???\n",
    "* сортировка - ???\n",
    "* sizeof - ???"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### unordered"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://en.cppreference.com/w/cpp/container/unordered_map\n",
    "    \n",
    "https://en.cppreference.com/w/cpp/container/unordered_set\n",
    "    \n",
    "https://en.cppreference.com/w/cpp/container/unordered_multimap\n",
    "\n",
    "https://en.cppreference.com/w/cpp/container/unordered_multiset"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Отображения / множества, основанные на значении хеш-функции от элементов.\n",
    "\n",
    "Обычно реализуются в виде массива списков (из-за специфики требований их сложно реализовать через открытую адресацию).\n",
    "\n",
    "(Не забыть рассказать про load_factor и rehashing)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](unordered_internals.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В качестве функции хеширования по умолчанию испольуется `std::hash`, но можно и задавать собственную функцию хеширования (аналогично собственной функции сравнения для `std::map`)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "std::unordered_map<int, std::string> id_to_name = {\n",
    "    {73, \"Balin\"},\n",
    "    {42, \"Dwalin\"},\n",
    "    {55, \"Gloin\"}\n",
    "};\n",
    "                \n",
    "// порядок перечисления объектов не гарантирован!\n",
    "for (const auto& [id, name] : id_to_name)\n",
    "    std::cout << id;\n",
    "    \n",
    "std::unordered_set<std::string> animals = {\"cat\", \"dog\", \"dolphin\"};\n",
    "                \n",
    "// порядок перечисления объектов не гарантирован!\n",
    "for (const auto& animal : animals)\n",
    "    std::cout << animal;\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Заполнение unordered-контейнера, обратить внимание на load_factor + rehash:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "std::unordered_set<int> ids;\n",
    "for (int i = 0; i < 1000; ++i)\n",
    "    ids.insert(generate_id());\n",
    "// Вопрос: сложность алгоритма в кол-ве копирований\n",
    "// Вопрос: сложность алгоритма в кол-ве аллокаций\n",
    "\n",
    "std::unordered_set<int> ids;\n",
    "ids.reserve(1000);\n",
    "for (int i = 0; i < 1000; ++i)\n",
    "    ids.insert(generate_id());\n",
    "// Вопрос: сложность алгоритма в кол-ве копирований\n",
    "// Вопрос: сложность алгоритма в кол-ве аллокаций\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Замечание__: если слегка ослабить требования к `unordered_*` контейнерам, например, разрешить протухать итераторам при вставке новых элементов, то hash-based отображения можно значительно (в разы) ускорить, что и было сделано сторонними реализациями.\n",
    "\n",
    "Например, реализация от google: https://www.youtube.com/watch?v=ncHmEUmJZf4\n",
    "\n",
    "И море, море их. Толковый обзорный доклад с деревом решений \"какой когда использовать\":\n",
    "https://www.youtube.com/watch?v=M2fKMP47slQ"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Стоимость:\n",
    "\n",
    "* расходы памяти на элемент - ???\n",
    "* поиск по значению - ???\n",
    "* вставка - ???\n",
    "* удаление - ???\n",
    "* сортировка - ???\n",
    "* sizeof - ???"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Замечания после лекции**:\n",
    "* убрать `valarray`, им никто не пользуется, да а объяснить идею его введения не получается, т.к. аудитория не знакома с векторизацией\n",
    "* картинка с итераторами у `std::list` непонятная (куда `begin`, куда `end`). Желательно найти получше или, кхм, самому нарисовать.\n",
    "* по `unordered`-контейнерам материал скомкан. Нужно оттачивать / расширять.\n",
    "* про in/out-итераторы не успели (и хорошо). Их нужно: а) выносить на конец, б) давать введение, что итератор - это класс, имеющий такие-такие методы, а их реализация может быть какой угодно (см. след. лекцию)."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
